1. Field of the Invention
The present invention relates generally to scheduling instructions for execution within a microprocessor, and, more particularly, to determining when these instructions are ready for execution prior to scheduling.
2. Description of the Related Art
A scheduler is the part of a microprocessor that is responsible for scheduling instructions for execution within a microprocessor's execution units. As a part of scheduling instructions, the scheduler preferably determines when an instruction is ready to be scheduled for execution. For purposes of this invention, the terms "scheduling for execution" and "scheduling for dispatch" are synonymous. One factor that affects whether an instruction is ready is the availability of resources, such as an execution unit. In present day microprocessors, there are different types of execution units, and each execution unit may generally execute only certain types of instructions. It is the scheduler that ascertains what type of instructions are ready for execution and whether execution units that may process these types of instructions are available.
Another factor that affects whether an instruction is ready for execution is whether the instruction's sources are available. An instruction's sources are the data that the instruction requires before it can be executed. An instruction is said to be dependent on earlier instruction when it cannot be executed until the earlier instruction has been executed. An example of this is when a first instruction calculates or stores results that are to be utilized by a later instruction. In this case, the later instruction cannot be scheduled for execution until the first instruction has executed. This dependency of a later instruction on data derived from an earlier instruction is commonly referred to as data dependency.
Prior microprocessors have addressed these scheduling issues with a device called a reservation station. A reservation station holds instructions while they await execution. Along with each instruction, the reservation station has a location that holds the instruction's source addresses. A source address is the address of the storage location from which the instruction's data will be transferred. Furthermore, the reservation station has a "ready" field that indicates when the source address is valid. Using such a reservation station, it is possible to accommodate the data dependencies discussed above. When an instruction requires the results of an earlier instruction, the valid bit for its source address is not set until it is determined that the prior instruction has stored its results in the storage location. Once an instruction's source addresses are valid, the instruction is ready to be dispatched for execution. This type of dependency is also called "source" or "data" dependency.
In today's high speed microprocessors, this reservation station approach has undesirable limitations. One of the problems is that each entry in the reservation station that is dependent on an earlier instruction is required to watch, or "snoop", the output of the execution units to determine when its sources are available. Furthermore, once it determines that its sources are valid, it then takes time to schedule the instruction for execution. It would be desirable to have a scheduler that knew when instructions were ready to be dispatched without having to snoop the output of the execution units.
Another problem with the approach discussed above is that a lag is created between a dependent instruction and the instruction upon which it is dependent The lag is created as follows: after an instruction executes, its results appear on the output bus of the execution unit. The reservation station watches this bus to determine when any required sources become available. If the output of the execution unit is required by an entry in the reservation station, the source bit for that entry is set. Once all source bits are set, an entry is ready to be dispatched for execution. There is a time lag between when the source data is generated by the execution unit and the time that the dependent instruction is considered ready. This time lag can easily constitute several clock cycles. It would be desirable to have a scheduler that knew how long it would take after a first instruction is dispatched for execution to be complete.
The present invention is directed to overcoming, or at least reducing the affects of, one or more of the problems set forth above.